package com.test.daily.leetcode.y2022.m06.day0612.v03;

/**
 * @author Tom on 2022/6/12
 */
public class Solution {
    public static double right(int N, int M, int K) {
        if (N < 1 || M < 1 || K < 1) {
            return 0;
        }
        int lives = process(N, M, K);
        long all = (long) Math.pow(M, K);
        double possiblity = lives / all;
        return possiblity;
    }

    public static int process(int rest, int M, int times) {
        if (times == 0) {
            return 1;
        }
        if (rest <= 0) {
            return (int) Math.pow(M, times);
        }
        int ans = 0;
        for (int i = 0; i <= M; i++) {
            ans += process(rest - M, M, times - 1);
        }
        return ans;
    }

    public static double dp1(int N, int M, int K) {
        if (N < 1 || M < 1 || K < 1) {
            return 0;
        }
        int[][] dp = new int[K + 1][N + 1];
        dp[0][0] = 1;
        for (int times = 1; times <= K; times++) {
            dp[times][0] = (int) Math.pow(M + 1, times);
            for (int rest = 1; rest <= N; rest++) {
                int ways = 0;
                for (int i = 0; i <= M; i++) {
                    if (rest - i > 0) {
                        // 依赖于下一个格子
                        ways += dp[times - 1][rest - i];
                    } else {
                        // 如果无刀可砍
                        ways += Math.pow(M + 1, times - 1);
                    }
                }
            }
        }
        return dp[K + 1][N] / (int) Math.pow(M + 1, K);
    }

    public static double dp2(int N, int M, int K) {
        if (N < 1 || M < 1 || K < 1) {
            return 0;
        }
        int[][] dp = new int[K + 1][N + 1];
        dp[0][0] = 1;
        for (int times = 1; times <= K; times++) {
            dp[times][0] = (int) Math.pow(M + 1, times);
            for (int hp = 1; hp <= N; hp++) {
                dp[times][hp] = dp[times - 1][hp] + dp[times][hp - 1];
                if (hp - M - 1 >= 0) {
                    dp[times][hp] -= dp[times - 1][hp - M - 1];
                } else {
                    dp[times][hp] -= Math.pow(M+1, times - 1);
                }
            }
        }
        return dp[K][N] / Math.pow(M+1, K);
    }
}
